""""1.老板有一袋金块(共n块)，最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，我们希望用最少的比较次数找出最重的金块。
用分治法解决该金块问题。用二分策略。"""
def find_max_min_binary(arr, low, high):
    """
    使用二分策略同时找到数组中的最大值和最小值
    返回: (最大值, 最小值)
    """
    # 当只有一个元素时
    if low == high:
        return arr[low], arr[low]

    # 当有两个元素时
    if high == low + 1:
        if arr[low] > arr[high]:
            return arr[low], arr[high]
        else:
            return arr[high], arr[low]

    # 分治：将数组分成两部分
    mid = (low + high) // 2
    left_max, left_min = find_max_min_binary(arr, low, mid)
    right_max, right_min = find_max_min_binary(arr, mid + 1, high)

    # 合并结果
    overall_max = left_max if left_max > right_max else right_max
    overall_min = left_min if left_min < right_min else right_min

    return overall_max, overall_min


# 测试金块问题的二分策略
def test_gold_binary():
    golds = [5, 2, 8, 1, 9, 3, 7, 4, 6]
    max_gold, min_gold = find_max_min_binary(golds, 0, len(golds) - 1)
    print(f"金块重量: {golds}")
    print(f"最重金块(二分策略): {max_gold}")
    print(f"最轻金块(二分策略): {min_gold}")
    print()


test_gold_binary()